package wedaex.helper;


/**
 * Calculate the Levenshtein Distance between two strings
 *
 * @author cedricho
 */
public class LevenshteinDistance {
	private String source;
	private String target;
	private int[][] matrix;

	public LevenshteinDistance(String source, String target) {
		this.source = source;
		this.target = target;
	}
	
	/**
	 * @return the Levenshtein Distance
	 */
	public int calculate() {
		matrix = new int[source.length()+1][target.length()+1];
		for (int i = 0; i < matrix.length; i++)
			matrix[i][0] = i;
		for (int j = 0; j < matrix[0].length; j++)
			matrix[0][j] = j;

		for (int i = 1; i < matrix.length; i++) {
			for (int j = 1; j < matrix[i].length; j++) {
				int cost = source.charAt(i-1)==target.charAt(j-1) ? 0 : 1;
				matrix[i][j] = minimum(
						matrix[i-1][j] + 1,		// deletion
						matrix[i][j-1] + 1,		// insertion
						matrix[i-1][j-1] + cost);	// substitution
			}
		}
		return matrix[source.length()][target.length()];
	}
	
	public int[][] getMatrix() {
		return matrix;
	}

	private int minimum(int i, int j, int k) {
		return Math.min(i, Math.min(j, k));
	}

	public static void main(String[] args) {
		String source = "@ 2007 John Resig and the";
		String target = "<p>&copy; 2007 <a href='http://ejohn.org/'>John Resig</a> and the <a href='http://docs.jquery.com/About/Contributors'>jQuery team</a>.</p>";
		LevenshteinDistance ld = new LevenshteinDistance(source, target);
		ld.calculate();
		int[][] m = ld.getMatrix();

		System.out.print("    ");
		for (int i = 0; i < target.length(); i++) {
			System.out.printf("%3s", target.charAt(i));
		}
		System.out.println();
		for (int i = 0; i < m.length; i++) {
			if(i==0)
				System.out.print(" ");
			else
				System.out.printf("%s", source.charAt(i-1));
			for (int j = 0; j < m[i].length; j++) {
				System.out.printf("%3d", m[i][j]);
			}
			System.out.println();
		}
	}
}
